Documents created in electronic form are often represented in a page description language (“PDL”), such as POSTSCRIPT, PCL, AgfaScript and IPDS. In a PDL representation, a document may be described in terms of commands that represent text and graphical objects. To view or print the document, the PDL commands are sent to a raster image processor (“RIP”), which interprets the PDL commands and generates electronic signals used by an output device to render the text and graphical objects. For example, the RIP may be part of a personal computer or workstation, and the output device may be a video display screen. Alternatively, the RIP may be part of a printer controller, and the output device may be a print engine. In either case, the RIP converts the PDL print stream to a raster bitmap.
A raster bitmap represents the pixels displayed or written by an output device and the values used to vary the pixel density. For example, if the density of an output device pixel can have either of two values (e.g., black or white), the bitmap requires one bit for each pixel. For color output devices, a unique bitmap is used for each colorant. Thus, for a print output device that uses cyan, magenta, yellow and black colorants, four bitmaps are used. Therefore, if a document includes an 8″×10″ color image at a resolution of 2400 dots/inch, the bitmap for each colorant includes more than 460 million pixels. To print each page of such a document on a high speed color printer (e.g., a 100 page per minute printer), the RIP must generate and provide to the print engine more than three billion bits per second. As a result, RIP processing time often is a bottleneck in achieving high-speed printing. To increase print speed, therefore, it is necessary to decrease the time required for the RIP to interpret a PDL data stream and generate each bitmap.
Previously known techniques for reducing RIP processing time have included parsing a PDL data stream into multiple segments, and then processing the various segments in parallel. For example, Vennekens U.S. Pat. No. 5,652,711 (“Vennekens”) describes methods for parallel processing a PDL data stream. In particular, Vennekens describes providing a PDL data stream that includes data commands and control commands to a master process, which divides the PDL data stream into independent data stream segments that are converted to intermediate data stream portions by multiple sub-processes. Data commands describe the data that must be reproduced by the output device, such as text, graphics and images, whereas control commands describe how the data must be reproduced, and may include font descriptions, page sections, forms and overlays. Each independent data stream segment includes data commands to describe the images included in a single page or region (i.e., a disjunctive portion of a physical medium), and also includes control commands to instruct how the data commands must be interpreted.
One disadvantage of this previously known method is its complexity. In particular, to maintain independence between each data stream segment, Vennekens' methods require that each segment know the appropriate “translation state” for the segment, which is composed of all previous control commands from the PDL data stream. To accomplish this goal, Vennekens describes several alternative methods. In one method, the master process builds a translation state description from the control commands in the PDL data stream, and then generates control commands to be included in the header of each independent data stream segment that describes the present translation state for that segment. Alternatively, the master process maintains a “master translation state” and a “common translation state,” which are built from control commands that have been processed by all sub-processes. Any sub-process that changes its translation state communicates the change to the master process via a control command reply. In turn, the master process then determines state changes based on differences between the current master translation state and the common translation state. The master process then uses the state changes to determine the control commands to be included in the next independent data stream segment to be generated.
In addition, to maintain independent data stream segments, Vennekens' methods include creating “extended control commands,” “version control commands,” “segment control commands,” and “sync control commands.” For some PDLs (e.g., POSTSCRIPT), however, it would be extremely difficult to implement such additional control commands and intra-process communication. In particular, for many existing PDLs, it would be necessary to modify the source code for the PDL interpreter to provide such commands. In most instances, such source code is unavailable for modification. Even if the source code is available, however, it may still be very complicated to retrofit the PDL interpreter to implement the type of system described by Vennekens.
Further, Vennekens' independent data stream segments each generate an intermediate data stream portion, and the various portions must be combined into a single intermediate data stream portion in the order of the original PDL data stream. However, some intermediate data stream portions may not be generated in the same chronological order as the segments were created. As a result, a combination process is required to rearrange the various intermediate data stream portions in the correct chronological order. This adds additional complexity to an already complicated process. Moreover, Vennekens' method appears to be limited to parsing a PDL data stream into non-overlapping regions of the document image, and provides no description of how it is possible to divide overlapping segments of an image between multiple processors.
In view of the foregoing, it would be desirable to provide improved methods and apparatus for parallel processing multiple segments of a PDL data stream.
It further would be desirable to provide methods and apparatus for parallel processing multiple segments of a PDL data stream, without requiring modification to the source code of a PDL interpreter.
It additionally would be desirable to provide methods and apparatus for parallel processing multiple segments of a PDL data stream in which the segments may represent overlapping portions of a document image.